1. Field of the Invention
The present invention relates to packet switching and routing systems, specifically to packet forwarding techniques.
2. Description of the Related Art
In data networks, Quality of Service (QoS) is a feature that allows network devices to drop packets on a selective basis to avoid or reduce congestion in the network. Generally, the elements of QoS include: “classification” and “policing”. Packets are classified into different traffic classes according to a policy defined by the network administrator. For each class of traffic, packets are processed based on certain policing parameters set by the network-administrator using a given policing algorithm. When packets conform to assigned ‘policing’ parameters, the packets are referred to as “in-profile” packets and when the packets do not conform to the ‘policing’ parameters, the packets are referred to as “out-of-profile” packets. The network device forwards or ‘permits’ ‘in-profile’ packets. “Out-of-profile” packets are dropped or marked. Marking of “out-of-profile” packets lowers the priority of the packets and increases the probability that another network device in the network may drop the packets. Packets that are dropped or marked by the network device are referred to as “policed” packets.
Various algorithms exist to perform the policing of packets. Each algorithm can be implemented in a network device using a logic-module referred to as a ‘policer’. The ‘policer’ performs certain computations according to an algorithm defined by the network administrator on all incoming packets. One such policer that limits the total number of bytes of all incoming packets in any defined interval of time is referred to as ‘token bucket policer’ or a ‘leaky-bucket regulator’. A token bucket policer in a network device regulates the incoming data by limiting the data from a given incoming port to a predefined maximum amount during any given time interval. A user can contract with the network administrator to allow certain bit rate through the incoming port of a given network device. In such case, the policer of the network device limits the number of bits of the incoming port during any given time interval ‘T’ to: [(T*contract-rate)+burst size]. Where the ‘contract-rate’ is the mean bit rate agreed upon by the user and the network administrator and the burst is the maximum number of bits allowed above the contract rate during any given time.
In token bucket metaphor, a token bucket (state variable) represents the amount of data that any given port can transmit during a given time interval through a network device. The token bucket has a specified capacity. The value of the token bucket is increased according to a predefined bit rate. The maximum value of the token bucket is the maximum burst size contracted by the user. In token bucket policer implementation, the incoming data at a given port is measured and compared against the token bucket. When the value of the token bucket is greater than the size of an incoming packet, the incoming packet is ‘permitted’ to traverse through the network device. When the value of the token bucket is less than the size of the incoming packet, the incoming packet is ‘policed’. When the packet is policed, the network device either drops the incoming packet or marks the incoming packet.
The conventional implementation of token bucket algorithm presents a problem when different sized packets arrive at a network device. When there is congestion in the network, the token bucket algorithm favors smaller sized packets over larger sized packets. Congestion occurs when the incoming data-rate is greater than the contract-rate. For example, when two users are coupled to a network device via a single port, both the users can send traffic on the ports. The traffic from both the users is policed according to the same policing scheme. During the congestion, if the users send different sized packets, the network device allows smaller sized packet to flow through and the larger sized packets are dropped. This can be illustrated by the following example.
Two users, A and B, are connected to a network device via a single port. The network device has one token bucket policer (TBP) for the port. The traffic from both the users is policed by the TBP. The TBP is configured to allow traffic with a contract rate of 10 Mbps. The traffic from user A includes 64 byte packets arriving at a speed of 11 Mbps. The traffic from user B includes 1K bytes packets arriving at 11 Mbps. The cumulative incoming traffic that is mapped to the TBP is 22 Mbps (11+11) which is greater than contract rate, 10 Mbps. Initially, the traffic from users A and B is permitted until a steady state is reached and bucket of the TBP is empty. The network device adds tokens into the token bucket according to the contracted rate. The incoming packets are held into an incoming buffer. When enough tokens are accumulated in the bucket, the 64 bytes packets from user A ‘sneaks’ through the network device because the packet size is smaller and the token bucket includes just enough tokens to allow the smaller packets. In such case, the 1K bytes packets from user B are always blocked (policed). Thus, once a steady state is reached, the traffic from user A is permitted (10 Mbps permitted, 1 Mbps policed) and the entire traffic from user B is policed.
Similarly, when a single token bucket policer is assigned to multiple incoming data flows with different sized packets (multiple users on single port, single user on multiple ports, multiple users on multiple ports or the like) and the incoming data is higher than the contract rate during a certain time window, the token bucket policer permits higher percentage of smaller sized packets as compared to larger sized packets during such time window.
A method of packet policing is needed that can eliminate the ‘bias’ for smaller sized packets and allow ‘unbiased’ forwarding of different sized packets during traffic congestion.